package com.azure.code.graph.kruskal;

import com.azure.code.graph.unionFind.UF;

/**
 * 那么最小生成树：在所有可能生成树中，权重和最小的那颗树就叫【最小生成树】
 * 一般来说，我们都是在无向加权图中计算最小生成树的，所有使用最小生成树算法的现实场景中，
 *  图的边权重一般代表成本、距离的标量
 *
 *  Kruskal算法是基于查并集的贪心算法
 *
 *  Kruskal 克鲁斯卡尔算法的基本思想是以边为主导地位，始终选择当前可用(所选的边不能构造回路)的最小权值边
 *  所以Kruskal算法的第一步是给所有的边按照从小到大的顺序排序。这一步可以直接使用qsort排序。
 *  接下来从小到大一次考察每一条边(u,v)
 *
 *  具体实现过程如下:
 *  a) 设一个有n个顶点的连通网络为G(V,E)，最初先构造一个只有n个顶点，没有边的非连通图T={V,空}，图中的每个顶点
 *     自成一格连通分量
 *  b) 在E中选择一条具有最小权值的边时，若该边的两个顶点若在不同的连通分量上，则将此边加入到T中；
 *     否则即这条边的两个顶点若在同一个连通分量上，则将此边舍去(此后永不选用这条边)，重新选择一条权重最小的边。
 *  c) 如果重复下去，知道所有的顶点在同一连通分量上为止
 *
 *  贪心思路：
 *   将所有边按照权重从小到大排序，从权重最小的边开始遍历，如果这条边和mst中的其他边不会形成环，
 *   则这条边是最小生成树的一部分，将它加入mst集合中；否则，这条边不是最小生成树的一部分，不要把
 *   它加入mst集合
 *
 */
public class Kruska_261 {

    // 判断输入若干个边是否能构造成一颗树
    boolean validTree(int n,int[][] edges){
        // 初始化 0...n-1条边
        UF uf = new UF(n);
        // 遍历所有的边，将组成边的两个节点进行链接
        for (int[] edge : edges) {
            int w = edge[0];
            int v = edge[1];
            // 若两个节点已经在同一个连通分量中，会产生环
            if(uf.connect(w,v)){
                return false;
            }
            // 这条边不会产生环，可以是树一部分
            uf.union(w,v);
        }
        return uf.count() == 1;
    }


}
